#include <iostream>
#include <vector>
#include <algorithm>
#include <list>

using namespace std;

vector<vector<int>> SumOfThreeNumber(vector<int> inputArray) {
    vector<vector<int>> resultArray;
    vector<int> tempArray;
    int length = inputArray.size();
    if (length < 3) {
        return resultArray;
    } else {
        sort(inputArray.begin(), inputArray.end());
        for (int i = 0; i <= length - 3; i++) {
            int low = i + 1;
            int high = length - 1;
            while (low < high) {
                int sum = inputArray[i] + inputArray[low] + inputArray[high];
                if (sum == 0) {
                    tempArray.push_back(inputArray[i]);
                    tempArray.push_back(inputArray[low]);
                    tempArray.push_back(inputArray[high]);
                    resultArray.push_back(tempArray);
                    tempArray.clear();
                    if (low + 1 < high && inputArray[low] == inputArray[low + 1]) {
                        low++;
                    } else if (high - 1 > low && inputArray[high] == inputArray[high - 1]) {
                        high--;
                    } else {
                        high--;
                    }
                } else if (sum > 0) {
                    high--;
                } else {
                    low++;
                }
            }
        }
        return resultArray;
    }
}


std::__cxx11::list<int> main() {
    vector<int> array = {1, 2, -3, -1, 0, 4};
    vector<vector<int>> resultArray = SumOfThreeNumber(array);
    for (int i = 0; i < resultArray.size(); ++i) {
        for (int j = 0; j < resultArray[i].size(); ++j) {
            cout << resultArray[i][j] << '\t';
        }
        cout << endl;
    }
    cout << endl;
    return 0;
}


public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> results = new LinkedList<>();
    //排序
    Arrays.sort(nums);
    for(int i = 0; i < nums.length - 2; i++){
        //小优化：如果第一个数就大于0，那就没必要再查找下去了
        if(nums[i] > 0) break;
        //考虑i的会重复  为什么重复的数不行？
        if(i > 0 && nums[i - 1] == nums[i]) continue;
        //定义两个指针，left指针，right指针，left为要查找的第二个数的坐标，right为要查找的第三个数的坐标
        int left = i + 1;
        int right = nums.length - 1;

        //left指针在这个过程中适当向右移，right指针也可能会向左移，但必须保证left在right的左边
        while(left < right){
            //三数之和有三种情况，三数之和大于0，三数之和小于0，三数之和等于0
            //1.三数之和大于0，right坐标的那个数太大了，要把它向左移一步
            if(nums[i] + nums[left] + nums[right] > 0){
                //向左移一步后有可能会等于left指针，也有可能会和后一个值重复，要去重
                while(left < right && nums[right] == nums[--right]);
            }
            //2.三数之和小于0，因为right坐标的数是三数中最大的，三数之和小于0就是因为左边left的那个数不够给力
            else if(nums[i] + nums[left] + nums[right] < 0){
                //左指针向右移一步后有可能会等于ringht指针，也有可能会和前一个值重复，要去重
                while(left < right && nums[left] == nums[++left]);
            }
            //3.三数之和等于0，添加到返回列表里面，并且同时将左指针右移，右指针左移，探索下一组适合的数据
            else if(nums[i] + nums[left] + nums[right] == 0){
                List<Integer> list = new LinkedList<>();
                list.add(nums[i]);
                list.add(nums[left]);
                list.add(nums[right]);
                results.add(list);
                while(left < right && nums[left] == nums[++left]);
                while(left < right && nums[right] == nums[--right]);
            }
        }
    }
    return results;
}

